\section{Conclusion}
We have analyzed two natural gossip-based discovery processes in
networks and showed almost-tight bounds on their convergence in
arbitrary networks.  Our processes are motivated by the resource
discovery problem in distributed networks as well as by the evolution
of social networks. While we have addressed the convergence problem to
a complete graph in this paper, it will be interesting to study other
relevant questions, especially in the context of social networks: (1)
How and when do well-connected clusters (communities) emerge?  (2)
When does the {\em clustering coefficient} become large? In
particular, can we generalize our results to obtain bounds on how long
it takes for evolving graphs to achieve a particular graph density or
clustering coefficient? (3) How does the diameter change with time? (4)
The triangulation and two-hop walks are both ``memoryless'' processes.
It has been shown recently that the inclusion of memory in
rumor-spreading can be beneficial in certain classes of
graphs~\cite{doerr+ff:rumor}.  Can adding memory to the two processes
we study have a similar effect?  These questions can lead to a better
understanding of how discovery processes influence the evolution of
social networks.
 
 We would like to study variants of the processes
that take into account failures associated with forming connections,
the joining and leaving of nodes, or having only a subset of
nodes to participate in forming connections.  We believe our
techniques can be extended to analyze such situations as well.  From a
technical standpoint, the main problem left open by our work is to
resolve the logarithmic factor gap between the upper and lower bounds.
It is not hard to show that from the perspective of increasing the
minimum degree by a constant factor, our analysis is tight up to
constant factors.  It is conceivable, however, that a sharper upper
bound can be obtained by an alternative analysis that uses a
``smoother'' measure of progress.
